The present invention relates to matrix decomposition.
It is sometimes desirable to decompose a matrix A into other matrices. There are many types of matrix decomposition, an example of which is QR decomposition. In QR decomposition, a matrix A (or X) is decomposed into an orthogonal matrix Q and an upper triangular matrix R, i.e., a matrix where for each column, each element below the diagonal element of the column has a value equal to zero. Thus, a matrix A is replaced by the product of matrices Q and R. In other words, A is equal to the product QR.
QR decomposition may be applicable in a situation where a known matrix A is multiplied by a column vector V (whose elements are variables which need to be calculated) and results in a known column vector Z. In other words, AV=Z, where A is an N by N matrix, and V and Z are N by 1 matrices, i.e., column vectors, where N is an integer greater than Such matrices may be used, for example, to solve a set of simultaneous equations, a situation which arises in many applications (e.g., digital pre-distortion (DPD), Mutiple-Input and Multiple-Output (MIMO), beamforming, radar, and imaging). Replacing QR for A results in the following: QRV=Z, which can be transformed to RV=Q−1Z. Q is known and, therefore, Q−1 is also known. Similarly, as noted above, Z is also known. Therefore, the product Q−1Z is also known and may be replaced by another known column vector Z′. Thus, RV=Z′. As both Z′ and R are known, and R is an upper triangular matrix, the variable values for column vector V can be easily calculated using back substitution.
There are a number of known methods for performing the QR decomposition. These methods include the Gram-Schmidt transformation, the Householder transformation, and the Givens rotation. The Givens rotation may be implemented using a systolic array. In such an implementation, different columns of the input matrix A or X are fed into different columns of the systolic array while column matrix Z is fed into another column of the systolic array. The cells in the systolic array may include hardware for performing a coordinate rotation digital computer (CORDIC) algorithm to accomplish the Givens rotations needed for the QR decomposition.
It is desirable to efficiently implement hardware for performing matrix decomposition. Such efficiency may, for example, be achieved by increasing throughput and decreasing resource usage.